package 数据结构.树;

import java.util.HashMap;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-05
 */
public class JZ84二叉树中和为某一值的路径3 {
    //两次遍历
    //递归
    private int res = 0;
    //dfs查询以某结点为根的路径数
    private void dfs(TreeNode root, int sum){
        if(root == null)
            return;
        //符合目标值
        if(sum == root.val)
            res++;
        //进入子节点继续找
        dfs(root.left, sum - root.val);
        dfs(root.right, sum - root.val);
    }
    //dfs 以每个结点作为根查询路径
    public int FindPath (TreeNode root, int sum) {
        //为空则返回
        if(root == null)
            return res;
        //查询以某结点为根的路径数
        dfs(root, sum);
        //以其子结点为新根
        FindPath(root.left, sum);
        FindPath(root.right, sum);
        return res;
    }

    //一次遍历+哈希表
    //记录路径和及条数
    private HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
    //last为到上一层为止的累加和
    private int dfs2(TreeNode root, int sum, int last){
        //空结点直接返回
        if(root == null)
            return 0;
        int res = 0;
        //到目前结点为止的累加和
        int temp = root.val + last;
        //如果该累加和减去sum在哈希表中出现过，相当于减去前面的分支
        if(mp.containsKey(temp - sum))
            //加上有的路径数
            res += mp.get(temp - sum);
        //增加该次路径和
        mp.put(temp, mp.getOrDefault(temp, 0) + 1);
        //进入子结点
        res += dfs2(root.left, sum, temp);
        res += dfs2(root.right, sum, temp);
        //回退该路径和，因为别的树枝不需要这边存的路径和
        mp.put(temp, mp.get(temp) - 1);
        return res;
    }

    public int FindPath2 (TreeNode root, int sum) {
        //路径和为0的有1条
        mp.put(0, 1);
        return dfs2(root, sum, 0);
    }
}
